home *** CD-ROM | disk | FTP | other *** search
/ Just Call Me Internet / Just Call Me Internet.iso / prog / atari / c / berm122 / patmat.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-16  |  2.9 KB  |  62 lines
  1. #include <stdio.h>
  2.  
  3. /* Function: patmat
  4.    Purpose : Regular Expression Pattern Matching
  5.    Author  : Sreenath Chary
  6.    Notice  : Quite brilliantly optimized by Arjen G. Lentz
  7.              (according to Mr. Lentz himself)
  8.    Usage   : Pass two string pointers as parameters.  The first being a raw
  9.              string & the second a pattern the raw string is to be matched
  10.              against.  If the raw string matches the pattern,then the function
  11.              returns 1, else it returns 0.
  12.  
  13.              e.g.  patmat("abcdefghi","*ghi")    returns a 1.
  14.                    patmat("abcdefghi","??c??f*") returns a 1.
  15.                    patmat("abcdefghi","*dh*")    returns a 0.
  16.                    patmat("abcdefghi","*def")    returns a 0.
  17.  
  18.              The asterisk is a wild card to allow any characters from its first
  19.              appearance to the next specific character.  The character ? is a
  20.              wild card for only one character in the position it appears.
  21.              Combinations such as "*?" or "?*" or "**" are illegal for obvious
  22.              reasons & the functions may goof, though I think it will still
  23.              work.
  24.  
  25.    Logic   : The only simple way I could devise is to use recursion.  Each
  26.              character in the pattern is taken & compared with the character in
  27.              the raw string.  If it matches then the remaining amount of the
  28.              string & the remaining amount of the pattern are passed as
  29.              parameters to patmat again until the end of the pattern.  If at
  30.              any stage the pattern does not match,then we go back one level &
  31.              at this level if the previous character was a asterisk in the
  32.              pattern, we hunt again from where we left off, otherwise we return
  33.              back one more level with a not found & the process goes on till
  34.              the first level call.
  35.  
  36.              Only one character at a time is considered, except when the
  37.              character is an asterisk. You'll get the logic as the program
  38.              unfolds.
  39. */
  40.  
  41. int patmat(char *raw, char *pat)      /* regular expression pattern matching */
  42. {
  43.         if (!*pat)                /* end of both is ok, only pat is mismatch */
  44.            return (!*raw);
  45.  
  46.         if (*pat == '*') {                                   /* wildcard '*' */
  47.            if (!*++pat)                                 /* last pat char? ok */
  48.               return (1);
  49.            do if ((*raw == *pat || *pat == '?') &&           /* match/wild ? */
  50.                   patmat(raw + 1,pat + 1))              /* match rest of pat */
  51.                  return (1);
  52.            while (*raw++);
  53.         }
  54.         else if (*raw && (*pat == '?' || *pat == *raw))      /* match/wild ? */
  55.            return (patmat(++raw,++pat));            /* try & match rest of it*/
  56.  
  57.         return (0);                                        /* no match found */
  58. }/*patmat()*/
  59.  
  60.  
  61. /* end of patmat.c */
  62.